package com.lwl.Algorithmic_data_structure.二叉树递归套路;

public class 二叉树节点最大距离 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public int maxDistance(TreeNode root){
        return process(root).maxDistance;
    }
    private Ret process(TreeNode root) {
        if (root == null){
            return new Ret(0,0);
        }
        Ret left = process(root.left);
        Ret right = process(root.right);
        int height = Math.max(left.height,right.height)+1;
        int maxDistance = Math.max(
                Math.max(left.maxDistance,right.maxDistance),
                left.height + right.height + 1);
        return new Ret(maxDistance,height);
    }
    class Ret{
        int maxDistance;//不一定途径自己
        int height;//一定途径自己
        public Ret(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }
}
